1. Field of the Invention
The present invention relates generally to computer cryptography, and more particularly to elliptic curve cryptosystems (ECC).
2. Related Art
A well-known and common method of public key cryptosystems uses a pair of keys, one public and one private. The keys may be mathematically related such that data encrypted with the public key may only be decrypted with the private key and conversely, data encrypted with the private key can only be decrypted with the public key. Encrypted data can be verified as authentic when decrypted with the sender's public key. Similarly, data signed with a private key may be verified with the signer's public key.
The process of using digital signatures is a well-known way to protect and ensure that electronic data maintains its integrity when transmitted. Conventionally, the contents of the electronic data to be signed are used to create a digest, for example, with a one-way hash function. The digest is then signed with the sender's private key. The recipient may then use the sender's public key to decrypt the signed digest, re-create a digest from the sent data, and if the two digests are identical, be assured that the data has not been altered during transmission.
Two common forms of public key cryptosystems, ECC and RSA, are well-known in the art, and are explained, for example, in U.S. Pat. No. 6,141,420 (the '420 patent), which is incorporated by reference herein.
As explained, for example, in the '420 patent, RSA security, where two prime numbers p and q are multiplied to provide a modulus n, is based on the integer factorization problem. A public key e and a private key d are related such that their product e·d equals 1 (mod φ) where φ=(p−1)(q−1). Using RSA security requires the transmission of the modulus n and the public key. The security of the system derives from the difficulty of factoring a large number that has no relatively small factors.
Accordingly both p and q must be relatively large primes (e.g. at least 512 bits). With the RSA protocol, this results in at least a 1024 bit modulus and a 512 bit public key, which require potentially significant bandwidth and storage capabilities. Such security calculations also require more processing time, especially as security standards change to require larger and larger keys. RSA security consequently often needs dedicated hardware to perform the necessary calculations.
Elliptic Curve Cryptosystem (ECC) provides an advantage over RSA by providing similar levels of security with much smaller keys, e.g. less than 1024 bits, and often on the order of 163 bits.
As explained, for example, in the '420 patent, ECC encryption may make use of the discrete logarithm problem, which assumes that G is a finite group, and that a and b are elements of C. Then the discrete logarithm problem for G is to determine a value x (when it exists) such that ax=b.
The effectiveness of using the discrete logarithm problem in encryption comes from the difficulty of determining the value x, which depends on the representation of G. For example, if an abstract cyclic group of order m is represented in the form of the integers modulo m, then the solution to the discrete logarithm problem reduces to the extended Euclidean algorithm, which is relatively easy to solve. However, the problem is made much more difficult if m+1 is a prime, and the group is represented in the form of the multiplicative group of the finite field Fm+1. The difficulty increases because the computations must be performed according to the special calculations required for operating in finite fields.
As further explained in the '420 patent, one known way to increase this difficulty is to use computations in a finite field whose members lie on an elliptic curve, that is by defining a group structure G on the solutions of y2+xy=x3+ax2+b over a finite field. The security provided by the use of elliptic curves is derived from the characteristic that an addition of two points on the curve can be defined as a further point that itself lies on the curve. Likewise the result of the addition of a point to itself will result in another point on the curve. Therefore, by selecting a starting point on the curve and multiplying it by an integer, a new point is obtained that lies on the curve. This means that where P=(x,y) is a point on an elliptic curve over a finite field [E(Fqa)], with x and y each represented by a vector of n elements then, for any other point Rε<P> (the subgroup generated by P), dP=R. To attack such a scheme, the task is to determine an efficient method to find an integer d, O≦d≦(order of P)−1 such that dP=R. To break such a scheme, the best algorithms known to date have running times no better than O(√{square root over (p)}), where p is the largest prime dividing the order of the curve (the number of points on the curve).
Thus, in a cryptographic system where the integer d remains secret, the difficulty of determining d can be exploited. Conventionally, in ECC signature generation, an elliptic curve is selected and a point P=(x,y), known as the generating point, is selected. Next, the sender chooses a random integer k as his private key. The sender then computes a point Q, Q=kP, which is another point on the curve, which becomes his public key that is made available to the receiver and the public. Although the receiver knows the value Q, due to the characteristic of elliptic curves noted above, he has great difficulty determining the private key k.
However, the generation of the public key from the one-time private key can take a considerable amount of time, and ECC may require a relatively large number of calculations.
What is needed then is an improved method of using ECC for digital signing that overcomes the shortcomings of conventional solutions.